use std::cmp::min;

const MONEYS: [usize; 8] = [1, 2, 5, 10, 20, 30, 50, 100];

pub fn dp_rec_mc(amount: u32) -> u32 {
    let mut dp = (0..(amount+1) as usize)
        .map(|_| amount as usize + 1)
        .collect::<Vec<usize>>();
    dp[0] = 0;
    for i in 1..dp.len() {
        for m in MONEYS {
            if i >= m {
                dp[i] = min(dp[i - m] + 1, dp[i])
            }
        }
    }
    dp[amount as usize] as u32
}
